/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: ling
 * Date: 2022-10-12
 * Time: 16:29
 */

/**
 * 假设你有一个特殊的键盘，上面只有四个键，它们分别是：
 *
 * 1、A 键：在屏幕上打印一个 A。
 *
 * 2、Ctrl-A 键：选中整个屏幕。
 *
 * 3、Ctrl-C 键：复制选中的区域到缓冲区。
 *
 * 4、Ctrl-V 键：将缓冲区的内容输入到光标所在的屏幕上。
 *
 * 这就和我们平时使用的全选复制粘贴功能完全相同嘛，只不过题目把 Ctrl 的组合键视为了一个键。现在要求你只能进行 N 次操作，请你计算屏幕上最多能显示多少个 A？
 * 链接：https://leetcode.cn/problems/4-keys-keyboard/
 * 题解：https://leetcode.cn/problems/4-keys-keyboard/
 *
 */
public class MaxA {
    /**
     * 法一：递归版动规，但是会超时，就算用备忘录去重，也会超时，所以就不加了，看看思路就行
     * dp(n - 1, a_num + 1, copy),    # A
     * 解释：按下 A 键，屏幕上加一个字符
     * 同时消耗 1 个操作数
     *
     * dp(n - 1, a_num + copy, copy), # C-V
     * 解释：按下 C-V 粘贴，剪切板中的字符加入屏幕
     * 同时消耗 1 个操作数
     *
     * dp(n - 2, a_num, a_num)        # C-A C-C
     * 解释：全选和复制必然是联合使用的，
     * 剪切板中 A 的数量变为屏幕上 A 的数量
     * 同时消耗 2 个操作数
     */
    public int maxADP(int n){
        return dp(n,0,0);
    }
    public int dp(int n,int a_num,int copy) {
        if(n<=0) {
            return a_num;
        }
        return max(dp(n-1,a_num+1,copy),
                dp(n-1,a_num+copy,copy),
                dp(n-2,a_num,a_num));
    }
    public int max(int a,int b,int c) {
        return Math.max(a,Math.max(b,c));
    }
    /**
     * 法二：动态规划
     * 这个算法基于这样一个事实，最优按键序列一定只有两种情况：
     *
     * 要么一直按 A：A,A,…A（当 N 比较小时）。
     *
     * 要么是这么一个形式：A,A,…C-A,C-C,C-V,C-V,…C-V（当 N 比较大时）。
     *
     * 因为字符数量少（N 比较小）时，C-A C-C C-V 这一套操作的代价相对比较高，可能不如一个个按 A；而当 N 比较大时，后期 C-V 的收获肯定很大。这种情况下整个操作序列大致是：开头连按几个 A，然后 C-A C-C 组合再接若干 C-V，然后再 C-A C-C 接着若干 C-V，循环下去。
     *
     * 换句话说，最后一次按键要么是 A 要么是 C-V。明确了这一点，可以通过这两种情况来设计算法：
     * int[] dp = new int[N + 1];
     * // 定义：dp[i] 表示 i 次操作后最多能显示多少个 A
     * for (int i = 0; i <= N; i++)
     *     dp[i] = max(
     *             这次按 A 键，
     *             这次按 C-V
     *         )
     *         对于「按 A 键」这种情况，就是状态 i - 1 的屏幕上新增了一个 A 而已，很容易得到结果：
     *         // 按 A 键，就比上次多一个 A 而已
     * dp[i] = dp[i - 1] + 1;
     * 但是，如果要按 C-V，还要考虑之前是在哪里 C-A C-C 的。
     *
     * 刚才说了，最优的操作序列一定是 C-A C-C 接着若干 C-V，所以我们用一个变量 j 作为若干 C-V 的起点。那么 j 之前的 2 个操作就应该是 C-A C-C 了：
     */
    public int maxA(int n) {
        int[] dp=new int[n+1];
        for(int i=1;i<=n;i++) {
            // 按 A 键
            dp[i]=dp[i-1]+1;
            for(int j=2;j<i;j++) {
                // 全选 & 复制 dp[j-2]，连续粘贴 i - j 次
                // 屏幕上共 dp[j - 2] * (i - j + 1) 个 A
                dp[i]=Math.max(dp[i],dp[j-2]*(i-j+1));

            }
        }
        return dp[n];
    }
}
